#pragma once

namespace xyx
{
    template<class K>
    struct BSTreeNode
    {
        BSTreeNode* _left;
        BSTreeNode* _right;
        K _key;

        BSTreeNode(const K& key)
            :_left(nullptr)
            , _right(nullptr)
            , _key(key)
        {
        }
    };


    template<class K>
    class BSTree
    {
    public:
        typedef BSTreeNode<K> Node;
        BSTree()
            :_root(nullptr)
        {}

        BSTree(const BSTree<K>& t)
        {
            _root = copy(t._root);
        }

        ~BSTree()
        {
            destory(_root);
        }

        BSTree<K>& operator=(const BSTree<K>& t)
        {
            swap(_root,t._root);
            return *this;
        }

        bool insert(const K& key)
        {
            //root为空
            if (_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }
            //root不为空
            Node* cur = _root;
            Node* parent = nullptr;

            while (cur)
            {
                if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else
                {
                    return false;
                }
            }
            cur = new Node(key);
            if (cur->_key > parent->_key)
                parent->_right = cur;
            else
                parent->_left = cur;

            return true;
        }

        bool find(const K& key)
        {
            Node* parent = nullptr;
            Node* cur = _root;

            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return true;
                }
            }

            return false;
        }


        bool erase(const K& key)
        {
            Node* parent = nullptr;
            Node* cur = _root;

            //找到删除的位置
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else//找到了
                {
                    //左为空
                    if (cur->_left == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else
                        {
                            if (parent->_left == cur)
                            {
                                parent->_left = cur->_right;
                            }
                            else
                            {
                                parent->_right = cur->_right;
                            }
                        }
                    }
                    else if (cur->_right == nullptr)//右为空
                    {
                        if (_root == cur)
                        {
                            _root = cur->_left;
                        }
                        else
                        {
                            if (parent->_left == cur)
                            {
                                parent->_left = cur->_left;
                            }
                            else
                            {
                                parent->_right = cur->_left;
                            }
                        }
                    }
                    else//左右不为空
                    {
                        Node* parent = cur;
                        Node* leftmax = cur->_left;
                        while (leftmax->_right)
                        {
                            parent = leftmax;
                            leftmax = leftmax->_right;
                        }

                        swap(leftmax->_key, cur->_key);

                        if (parent->_left == leftmax)
                        {
                            parent->_left = leftmax->_left;
                        }
                        else
                        {
                            parent->_right = leftmax->_left;
                        }
                        cur = leftmax;
                    }
                    delete cur;
                    return true;
                }
            }
            return false;
        }

        bool eraseR(const K& key)
        {
            _eraseR(_root,key);
        }

        void inorder()
        {
            _inorder(_root);
            cout << endl;
        }

        bool findR(const K& key)
        {
            return _findR(_root,key);
        }

        bool insertR(const K& key)
        {
            return _insertR(_root,key);
        }
    private:
        Node* copy(Node* root)
        {
            if(root == nullptr)
                return nullptr;

            Node* copyroot = new Node(root->_key);
            copyroot->_left = copy(root->_left);
            copyroot->_right = copy(root->_right);
            return copyroot;
        }

        void destory(Node* root)
        {
            if(root == nullptr)
                return;

            destory(root->_left);
            destory(root->_right);
            delete root;
        }

        bool _eraseR(Node*& root, const K& key)
        {
            if(root == nullptr)
                return false;
            
            if(root->_key > key)
                return _eraseR(root->_left,key);
            else if(root->_key < key)
                return _eraseR(root->_right,key);
            else
            {
                //提前保存结点避免删除找不到
                Node* del = root;
                //1.左为空 2.右为空 3.都不为空

                if(root->_left == nullptr)
                {
                    root = root->_right;
                }
                else if(root->_right == nullptr)
                {
                    root = root->_left;
                }
                else
                {
                    Node* leftmax = root->_left;
                    while(leftmax->_right)
                    {
                        leftmax = leftmax->_right;
                    }

                    swap(leftmax->_key,root->_key);
                    
                    return _eraseR(root->_left,key);
                }
                delete del;
                return true;
            }
        }

        bool _insertR(Node*& root, const K& key)
        {
            if(root == nullptr)
            {
                root = new Node(key);
                return true;
            }

            if(root->_key > key)
                return _insertR(root->_left,key);
            else if(root->_key < key)
                return _insertR(root->_right,key);
            else
                return false;

        }

        bool _findR(Node* root, const K& key)
        {
            if(root == nullptr)
                return false;
            
            if(root->_key > key)
                return _findR(root->_left,key);
            else if(root->_key < key)
                return _findR(root->_right,key);
            else
                return true;                
        }

        void _inorder(Node* root)
        {
            if (root == nullptr)
                return;


            _inorder(root->_left);
            cout << root->_key << " ";
            _inorder(root->_right);
        }

    private:
        Node* _root;
    };

    void testBST1()
    {
        BSTree<int> bst;
        int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
        for (auto& e : a)
        {
            bst.insert(e);
        }

        cout << bst.findR(4) << endl;
        cout << bst.findR(41) << endl;   
        cout << bst.findR(17) << endl;

        bst.inorder();
        
        bst.erase(8);
        bst.inorder();

        bst.erase(6);
        bst.inorder();

        bst.erase(7);
        bst.inorder();

        //for (auto& e : a)
        //{
        //    bst.erase(e);
        //}
        //bst.inorder();
    }

    void testBST2()
    {
        BSTree<int> bst;
        int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
        for (auto& e : a)
        {
            bst.insertR(e);
        }
        
        bst.inorder();

        bst.eraseR(8);
        bst.inorder();

        bst.eraseR(6);
        bst.inorder();

        bst.eraseR(7);
        bst.inorder();

        for (auto e : a)
        {
            bst.eraseR(e);
        }
        bst.inorder();
    }

    void testBST3()
    {
        BSTree<int> bst1;
        int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
        for (auto& e : a)
        {
            bst1.insertR(e);
        }
        bst1.inorder();
        BSTree<int> bst2(bst1);
        bst2.inorder();
        BSTree<int> bst3 = bst2;
        bst3.inorder();
        

    }

}